#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 743. 网络延迟时间
class Solution1
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> dist(n, vector<int>(n, INF));
        for(auto& t : times)
        {
            int src = t[0] - 1;
            int dst = t[1] - 1;
            dist[src][dst] = t[2];
        }

        for(int k = 0; k < n; ++k)
        {
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int ret = 0;
        dist[k - 1][k - 1] = 0;

        for(int i = 0; i < n; ++i)
        {
            ret = max(ret, dist[k - 1][i]);
        }
        return ret == INF ? -1 : ret;
    }
};

// 787. K 站中转内最便宜的航班
class Solution2
{
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) 
    {
        const int INF = 0x3f3f3f3f;
        vector<int> dist(n, INF);
        dist[src] = 0;
        for(int i = 0; i < k + 1; ++i)
        {
            vector<int> clone(dist);
            bool flag = false;
            for(auto& flight : flights)
            {
                int x = flight[0];
                int y = flight[1];
                int w = flight[2];
                if(dist[y] > clone[x] + w)
                {
                    flag = true;
                    dist[y] = clone[x] + w;
                }
            }
            
            if(!flag) break;
        }

        return dist[dst] == INF ? -1 : dist[dst];
    }
};

// 753. 破解保险箱
class Solution3
{
public:
    string crackSafe(int n, int k) 
    {
        // k的n-1次方个节点，每个节点由k条出边，所以图有k的n次方条边
        int edgesNum = pow(k, n), nodeNum = pow(k, n - 1);
        // 数组node是用来存储每个节点的出边，出边有索引来表示，最大索引是k-1
        vector<int> node(nodeNum, k - 1);
        // 这里多出来的n-1，其实是因为要初始化第一个节点"00...0"
        string s(edgesNum + (n -1), '0');
        // index表示节点索引
        for(int i = n - 1, index = 0; i < s.size(); ++i)
        {
            int edge = node[index];
            s[i] = edge + '0';
            // 将使用过的出边删除
            --node[index];
            // 选择下一条出边
            index = (index * k + edge) % nodeNum;
        }

        return s;
    }
};